Genetic Algorithms (GAs) are stochastic global search heuristics inspired by the principles of natural evolution, specifically Darwinian "survival of the fittest" and genetic recombination.
1. Representation Frameworks
- Canonical GAs: Use binary or Gray string representations to encode decision variables.
- Real-Coded GAs (RCGAs): Directly manipulate floating-point vectors, often more efficient for continuous optimization.
2. The Evolutionary Loop
An iterative process of evaluation, selection, and reproduction. A critical concept is the distinction between the Genotype (the encoded bit string/chromosome) and the Phenotype (the decoded decision variable value in the actual problem space).
The mapping from a binary string to a real value $x \in [a, b]$ is given by:
$$x = a + \frac{decimal\_value \times (b - a)}{2^L - 1}$$
Where $L$ is the bit length of the chromosome.
Hamming Cliffs
Watch out for Hamming Cliffs in standard binary coding—situations where adjacent decimal numbers (like 7 and 8) have radically different binary bit patterns (
0111 vs 1000), making it difficult for the GA to perform localized searches.
Python Implementation: Binary-to-Real Decoding
Question 1
Why is Gray coding often preferred over standard binary coding in GAs?
Question 2
If the mutation probability (p) is set too high (e.g., p = 0.5), what is the likely result?
Case Study: Bridge Component Optimization
Read the scenario below and answer the questions.
You are optimizing the design of a bridge component where the decision variable is "Material Thickness".
- The thickness must be between 0.0mm and 10.23mm.
- You are using a Canonical GA with a 10-bit binary string representation.
Q
1. If an individual has the chromosome
0000000000, what is the decoded thickness?
Answer: 0.0mm
The binary string
The binary string
0000000000 equals 0 in decimal. Using the formula $x = a + \frac{decimal \times (b-a)}{2^L - 1}$, we get $0.0 + \frac{0 \times (10.23 - 0.0)}{1023} = 0.0$.
Q
2. Calculate the search precision (the smallest possible change in thickness) for this 10-bit setup.
Answer: 0.01mm
Precision is defined by the range divided by the maximum possible decimal value. $\frac{10.23 - 0}{2^{10} - 1} = \frac{10.23}{1023} = 0.01mm$.
Precision is defined by the range divided by the maximum possible decimal value. $\frac{10.23 - 0}{2^{10} - 1} = \frac{10.23}{1023} = 0.01mm$.
Q
3. During selection, Individual A has fitness 10 and Individual B has fitness 30. Using Roulette Wheel selection, what is the probability B is chosen over A?
Answer: 75%
Total fitness = $10 + 30 = 40$. Probability of selecting B = $\frac{30}{40} = 0.75$ or 75%. (A 3:1 ratio).
Total fitness = $10 + 30 = 40$. Probability of selecting B = $\frac{30}{40} = 0.75$ or 75%. (A 3:1 ratio).